package P2分治回溯;

import java.util.TreeSet;

//全排列问题
public class FullPermutation {
    public static void main(String[] args) {
        String s = "ABC";
        char[] arr = s.toCharArray();
        TreeSet<String> set = new TreeSet<>();
        permutation(arr, 0, arr.length - 1, set);
        System.out.println(set);
    }

    private static void permutation(char[] arr, int from, int to, TreeSet<String> set) {
        if (from == to) {
            set.add(String.valueOf(arr));
        } else {
            for (int i = from; i <= to; i++) {
                //让i对应的字母做当前区间的老大=> arr[from]
                swap(arr, i, from);
                //计算下一个区间的情况
                permutation(arr, from + 1, to, set);
                //在保证原先顺序的情况下 进行交换 所以需要恢复原状
                swap(arr, i, from);
            }
        }
    }

    private static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
